翻訳と辞書 Words near each other ・ Pollard (surname) ・ Pollard Banknote ・ Pollard Baptist Church ・ Pollard baronets ・ Pollard Glacier ・ Pollard Hopewell ・ Pollard Kot ・ Pollard Meadows, Edmonton ・ Pollard railway station ・ Pollard script ・ Pollard Syndrum ・ Pollard's Chicken ・ Pollard's kangaroo algorithm ・ Pollard's p − 1 algorithm ・ Pollard's rho algorithm ・ Pollard's rho algorithm for logarithms ・ Pollard, Alabama ・ Pollard, Arkansas ・ Pollard, Kansas ・ Pollard, Washington ・ Pollard-Nelson House ・ Pollarding ・ Pollards Corner, Virginia ・ Pollards Hill ・ Pollards Point ・ Pollari ・ Pollatoomary ・ Pollawat Pinkong ・ Pollaxe ・ Pollaxe (disambiguation) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Pollard's rho algorithm for logarithms ： ウィキペディア英語版 Pollard's rho algorithm for logarithms Pollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem. The goal is to compute $\backslash gamma$ such that $\backslash alpha\; ^\; \backslash gamma\; =\; \backslash beta$, where $\backslash beta$ belongs to a cyclic group $G$ generated by $\backslash alpha$. The algorithm computes integers $a$, $b$, $A$, and $B$ such that $\backslash alpha^a\; \backslash beta^b\; =\; \backslash alpha^A\; \backslash beta^B$. Assuming, for simplicity, that the underlying group is cyclic of order $n$, we can calculate $\backslash gamma$ as a solution of the equation $(B-b)\backslash gamma\; =\; (a-A)\; \backslash pmod$. To find the needed $a$, $b$, $A$, and $B$ the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence $x\_i\; =\; \backslash alpha^\; \backslash beta^$, where the function $f:\; x\_i\; \backslash mapsto\; x\_$ is assumed to be random-looking and thus is likely to enter into a loop after approximately $\backslash sqrt\}$ steps. One way to define such a function is to use the following rules: Divide $G$ into three disjoint subsets of approximately equal size: $S\_0$, $S\_1$, and $S\_2$. If $x\_i$ is in $S\_0$ then double both $a$ and $b$; if $x\_i\; \backslash in\; S\_1$ then increment $a$, if $x\_i\; \backslash in\; S\_2$ then increment $b$. ==Algorithm== Let $G$ be a cyclic group of order $p$, and given $\backslash alpha,\; \backslash beta\backslash in\; G$, and a partition $G\; =\; S\_0\backslash cup\; S\_1\backslash cup\; S\_2$, let $f:G\backslash to\; G$ be a map $$ f(x) = \left\\right. and define maps $g:G\backslash times\backslash mathbb\backslash to\backslash mathbb$ and $h:G\backslash times\backslash mathbb\backslash to\backslash mathbb$ by $$ g(x,n) = \left\\right. $$ h(x,n) = \left\\right. :Inputs ''a'': a generator of ''G'', ''b'': an element of ''G'' :Output An integer ''x'' such that ''ax = b'', or failure :# Initialise ''a0'' ← 0 :#::''b0'' ← 0 :#::''x0'' ← 1 ∈ ''G'' :#::''i'' ← 1 :# ''xi'' ← ''f(xi-1)'', ''ai'' ← ''g(xi-1,ai-1)'', ''bi'' ← ''h(xi-1,bi-1)'' :#''x2i'' ← ''f(f(x2i-2))'', ''a2i'' ← ''g(f(x2i-2),g(x2i-2,a2i-2))'', ''b2i'' ← ''h(f(x2i-2),h(x2i-2,b2i-2))'' :# If ''xi'' = ''x2i'' then :## ''r'' ← ''bi'' - ''b2i'' :## If r = 0 return failure :## x ← ''r -1 ''(''a2i'' - ''ai'') mod ''p'' :## return x :# If ''xi'' ≠ ''x2i'' then ''i'' ← ''i+1'', and go to step 2. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pollard's rho algorithm for logarithms」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.